import copy
import math
from collections import Counter
from functools import cache
from heapq import heappop, heappush
from typing import List, Optional
from Algorithm.Factorial import Factorial
from TreeNode import TreeNode
from sortedcontainers import SortedDict

temp = '''
distance[i][j]表示i与j的距离
'''
MODE = 10**9 + 7
INT = 10**6
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        distance = [[INT for _ in range(n)] for _ in range(n)]
        for i in range(n):
            distance[i][i] = 0
        for edge in edges:
            distance[edge[0]][edge[1]] = edge[2]
            distance[edge[1]][edge[0]] = edge[2]
        #floyd 求最短路
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])

        min_count = INT
        min_node = 0
        for i in range(n):
            cnt = 0
            for j in range(n):
                if i == j:
                    continue
                if distance[i][j] <= distanceThreshold:
                    cnt += 1
            if cnt <= min_count:
                min_count = cnt
                min_node = i
        return min_node

    # 3123. 最短路径中的边
    def findAnswer(self, n: int, edges: List[List[int]]) -> List[bool]:
        edge_list = [[] for _ in range(n)]
        for i in range(len(edges)):
            x, y, w = edges[i]
            edge_list[x].append([y, w, i])
            edge_list[y].append([x, w, i])
        # Dijkstra 求0到其他节点的最短距离
        min_dis = [MODE] * n
        min_dis[n - 1] = 0
        priority_queue = [(0, n - 1)]
        while len(priority_queue) != 0:
            dis, x = heappop(priority_queue)
            if dis > min_dis[x]:
                continue
            for y, w, i in edge_list[x]:
                new_dis = dis + w
                if (min_dis[y] == MODE or new_dis < min_dis[y]):
                    min_dis[y] = new_dis
                    heappush(priority_queue, (new_dis, y))
        res = [False] * len(edges)
        visited = [False] * n

        def dfs(node: int, parent: int) -> bool:
            nonlocal res
            visited[node] = True
            for next_node, next_w, i in edge_list[node]:
                if next_node == parent:
                    continue
                if min_dis[next_node] + next_w != min_dis[node]:
                    continue
                res[i] = True
                if not visited[next_node]:
                    dfs(next_node, node)

        dfs(0, -1)
        return res